/*
https://leetcode.cn/problems/count-special-integers/
统计特殊整数
转换为暴力dfs
*/
#define ll long long
class Solution {
public:
    string num;
    vector<int> st;
    ll find(int idx,bool fit,vector<int>& st,bool pre){
        ll res=0;
        if(idx==num.size()) return 1;
        int mx=(fit?(num[idx]-'0'):9);
        for(int i=0;i<=mx;i++){
            if(st[i]) continue;
            if(pre||i!=0)
            st[i]=true;
            res+=find(idx+1,fit&&(i==mx),st,pre||i);
            //if(!idx)cout<<i<<" "<<find(idx+1,fit&&(i==mx),st)<<endl;
            st[i]=false;
        }
        return res;
    }
    int countSpecialNumbers(int n) {
        st.resize(10,0);
        num="";
        while(n){
            num+='0'+n%10;
            n/=10;
        }
        reverse(num.begin(),num.end());
        return find(0,1,st,0)-1;
    }
};